#include "Tree.h"

void QueueInit(Queue *pq)
{
    assert(pq);
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue *pq)
{
    assert(pq);
    QNode *cur = pq->phead;
    while (cur)
    {
        QNode *next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}
void QueuePush(Queue *pq, QDatatype x)
{
    assert(pq);
    QNode *newnode = (QNode *)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("newnode malloc :");
        return;
    }
    newnode->val = x;
    newnode->next = NULL;
    if (pq->ptail)
    {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    else
    {
        pq->phead = pq->ptail = newnode;
    }
    pq->size++;
}
bool QueueEmpty(Queue *pq)
{
    assert(pq);
    return pq->size == 0;
}
void QueuePop(Queue *pq)
{
    assert(pq);
    // assert(!QueueEmpty(pq));
    assert(pq->phead != NULL);
    if (pq->phead->next == NULL)
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else
    {
        QNode *next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}
QDatatype QueueFront(Queue *pq)
{
    assert(pq);
    assert(pq->phead != NULL);
    return pq->phead->val;
}
QDatatype QueueBack(Queue *pq)
{
    assert(pq);
    assert(pq->ptail != NULL);
    return pq->ptail->val;
}
int QueueSize(Queue *pq)
{
    assert(pq);
    return pq->size;
}
BTNode *BinaryTreeCreate(BTDataType *a, int n, int *pi)
{
    if (a == NULL || n <= 0)
        return NULL;
    if (a[*pi] == ' ')
    {
        (*pi)++;
        return NULL;
    }
    BTNode *root = (BTNode *)malloc(sizeof(BTNode));
    root->val = a[(*pi)++];
    root->left = BinaryTreeCreate(a, n, pi);
    root->right = BinaryTreeCreate(a, n, pi);
    return root;
}
void BinaryTreeDestroy(BTNode **root)
{
    if ((*root) == NULL)
        return;
    BinaryTreeDestroy(&(*root)->left);
    BinaryTreeDestroy(&(*root)->right);
    free(*root);
    *root = NULL;
}
int BinaryTreeSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeLeafSize(BTNode *root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelKSize(BTNode *root, int k)
{
    assert(k > 0);
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
BTNode *BinaryTreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->val == x)
        return root;
    BTNode *left = BinaryTreeFind(root->left, x);
    if (left)
        return left;
    BTNode *right = BinaryTreeFind(root->right, x);
    if (right)
        return right;
    return NULL;
}
void BinaryTreePrevOrder(BTNode *root)
{
    if (root == NULL)
    {
        return;
    }
    printf("%c ", root->val);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}
void BinaryTreeInOrder(BTNode *root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreeInOrder(root->left);
    printf("%c ", root->val);
    BinaryTreeInOrder(root->right);
}
void BinaryTreePostOrder(BTNode *root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->val);
}

bool BinaryTreeComplete(BTNode *root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
            printf("%c ", front->val);
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }
        while (!QueueEmpty(&q))
        {
            BTNode *front = QueueFront(&q);
            if (front)
            {
                QueueDestroy(&q);
                return false;
            }
        }
    }
    QueueDestroy(&q);
    return true;
}